#include <iostream>
using  namespace std;
typedef struct Node
{
    int data;
    Node* pre;
    Node* next;
    //无参构造
    Node()
    {

    }
    Node(int n)
    {
        this->data=n;
        this->next=NULL;
        this->pre=NULL;
    }


};
void init(Node* & head)
{
   head=new Node;
   Node* pre=head;
   Node* p=NULL;
   int n;
   cin>>n;

   while(n--)
   {
       int x;
       cin>>x;
       p=new Node(x);
       pre->next=p;
       p->pre=pre;
       pre=p;
   }
   head->pre=p;
   p->next=head;
}
void print(Node* head)
{
    Node* p=head->next;
    while(p!=head)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}
//按照左边的链域打印
void printLlink(Node* head)
{
    Node* p=head->pre;
    while(p!=head)
    {
        cout<<p->data<<" ";
        p=p->pre;
    }
    cout<<endl;

}
//左链域有序
void SortLink(Node* head)
{
    Node* p=head->next->next;//指向第二个结点
    head->pre=head->next;//头节点和第一个结点形成封闭有序区间
    //将无序区的元素一个个加入到有序区间一直到p=head为止
    //右链域一直保持正常
    while(p!=head)
    {
        Node* f=head;
        Node* r=head->pre;
        //让f和r一起动  直到r等于head;停止
        while(p->data>r->data&&r!=head)
            {
                r=r->pre;
                f=f->pre;
            }
            //退出之后 将p插入到 f和r之间
        p->pre=f->pre;
        f->pre=p;
        p=p->next;
    }
}

int main() {

    Node* head=NULL;
    init(head);
    print(head);
    SortLink(head);
   printLlink(head);


    return 0;
}
